package com.dmall.sort.algorithm;

import java.util.Random;

/**
 * 插入快速排序算法
 * @author xiao1.wang
 * @date 2021/10/7 22:35
 */
@SuppressWarnings("all")
public class Insertion2WaysQuickSort implements Sort {
    private static final Random RANDOM = new Random();
    private static final int INSERTION_THRESHOLD = 32;

    @Override
    public void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    private void quickSort(int[] arr, int l, int r) {
        if (r - l <= INSERTION_THRESHOLD) {
            InsertionSort.insertionSort(arr, l, r);
            return;
        }
        int partition = partition(arr, l, r);
        quickSort(arr, l, partition - 1);
        quickSort(arr, partition + 1, r);
    }

    private int partition(int[] arr, int l, int r) {
        int random = RANDOM.nextInt(r - l + 1) + l;
        swap(arr, random, r);

        // arr[l+1...i-1] <= v; arr[j+1...r] >= v
        int i = l + 1, j = r;
        while (true) {
            while (i <= j && arr[i] < arr[l]) {
                i ++;
            }
            while (i <= j && arr[j] > arr[l]) {
                j --;
            }
            if (i >= j) {
                break;
            }
            swap(arr, i, j);
            i ++;
            j --;
        }
        swap(arr, l, j);
        return j;
    }

    @Override
    public String getName() {
        return "插入双路快速排序";
    }
}
